1. Field of the invention
The present invention relates to the field of computer networking. More particularly, the present invention relates to a method for transmitting delay sensitive information over systems using both Internet Protocol and Frame Relay.
2. The Background Art
Modern computer networks are divided up into layers. Each layer is responsible for providing some service to the layer above it, and may use the services of the layer below it. The International Standards organization (ISO) defined seven layers as a standard for computer networks. This standard is depicted in FIG. 1 at reference numeral 10. The layers are defined as follows:
(1) A physical layer, which is responsible for transmitting unstructured bits of information across a link.
(2) A data link layer, which transmits chunks of information across a link.
(3) A network layer, which is responsible for ensuring that any pair of systems in the network can communicate with each other.
(4) A transport layer, which establishes a reliable communications stream between a pair of systems.
(5) A session layer, which offers services above the simple full-duplex reliable communication stream provided by the transport layer.
(6) A presentation layer, which is responsible for providing a means by which applications can agree on representations of data.
(7) An application layer, which runs applications.
An increase in the use of the Internet in the 1970""s made it necessary for a standard to be created for communications over the Internet. This was prompted by the fact that the Internet comprises what is essentially a huge number of smaller networks, each of the smaller networks possibly having different standards of communication. Therefore, the Internet Protocol Suite was created to establish a single standard of communicating over the Internet, while still allowing for individual networks to maintain their own standards of communications within their own networks.
The Internet Protocol Suite is depicted in FIG. 1 at reference numeral 12. It comprises several standards for many of the network layers defined by the OSI. The Internet Protocol Suite standard for use with the network layer is called the Internet Protocol (IP), depicted at reference numeral 14 of FIG. 1. IP provides fragmentation and reassembly of data as well as error reporting and, along with TCP, is the heart of the Internet Protocol Suite.
IP works by splitting up data into IP packets, or chunks of information which contain not only the data to be transmitted but a variety of other information about the data as well. The IP Packet format is depicted in FIG. 2. The IP packet 20 contains the following fields:
(1) Version 22, which indicates the version of IP currently used.
(2) IP Header Length (IHL) 24, which indicates the packet header length in 32-bit words.
(3) Type-of-Service 26, which specifies how the upper layer protocol wants the packet to be handled.
(4) Total length 28, which indicates the length in bytes of the entire packet, including the header and data.
(5) Identification 30, which contains an integer identifying the packet, allowing for packets to be reassembled upon delivery.
(6) Flags 32, which indicate whether the packet can be fragmented and whether the packet is the last fragment in a series of fragmented packets.
(7) Fragment Offset 34,
(8) Time-to-live 36, which maintains a counter which gradually decrements down to zero at which point the packet is discarded, which keeps packets from looping infinitely.
(9) Protocol 38, which indicates which upper-layer protocol should receive the packet after IP processing is complete.
(9) Header checksum 40, which helps ensure IP header integrity.
(10) Source address 42, which specifies the sending node.
(11) Destination address 44, which specifies the receiving node.
(12) Options 46, which allows IP to support carious options, such as security.
(13) Data 48, which contains the information itself.
IP remains the standard for network layer communication over the Internet even today. Additionally many individual networks have also adopted the IP standard within their own network. IP remains the standard of choice for networks which utilize phone lines or other low speed, low reliability communications mediums, as it was designed with many safeguards to prevent errors.
Additionally, the use of IP packets allows a tremendous flexibility for a system to fragment data and send the packets in an order that maximizes efficiency. For example, if one user is sending an extremely large piece of information, while another was sending an extremely small piece of information, without fragmentation it would be possible for the user sending the extremely small piece of information to encounter an extremely large delay while the large piece of information was transmitted over the network. By fragmenting the large piece of information into packets, however, it is possible for the system to implement a feature wherein access to the bandwidth of the network is rotated evenly from user to user. This would mean that a portion of the large piece of information is sent, then the small piece of information is sent, then the rest of the large piece of information is sent. Thus, routers were designed with just such a feature, where access to the network was cycled between the users in equal doses.
A problem arises, however, in the transmission of voice, audio, video, or other delay sensitive information, over IP. IP was designed for the transmission of data, not voice. When transmitting data, delays, while annoying, normally do not affect the usefulness of the data. Unlike data, however, voice is delay sensitive. When talking on the phone, a delay of even a second between transmission and receipt can interrupt a conversation. In addition, there is a necessity in voice communication for two way simultaneous transmissions. For example, it is quite common for two people to speak at the same time during a conversation. Because of these requirements, it is necessary for voice to have simultaneous or near-simultaneous transmissions. Placing voice transmissions on the same level with data transmissions would result in ineffective voice transmission.
There are other types of delay sensitive information that are sometimes transmitted over networks. These can include such things as real-time video transmissions, interactive video game transmissions, and the like. Delay sensitive information is any information whose usefulness may be diminished significantly by delays in transmission. The main type of delay sensitive information is voice, but the same techniques used to handle voice information may be used to handle other types of delay sensitive information as well.
In order to remedy the problem of transmitting voice sensitive information over IP, two different solutions were developed. In the first, one of the type-of-service bits 26 is used to signify whether the data is delay sensitive or not. Thus, a network device supporting delay-sensitive transmission will look to this bit to determine what precedence to give the data in the queue holding data waiting for transmission over the network.
The second solution developed for the transmission of voice over IP involves the use of a Resource Reservation Protocol (RSVP). In these systems, in order to successfully transmit voice from one node to another, every node in the chain must be one that honors the RSVP system. Then, before transmission occurred, each node in the chain would be contacted and told to reserve a certain amount of bandwidth for the incoming transmission. After each node complied, the conversation could be initiated. FIG. 3 depicts an example of an IP network 60. For simplicity, this network 60 may be thought of as the Internet, with node A 62, node B 64, node C 66, and node D 68. These nodes 62, 64, 66, 68 may be Internet domains, each containing a subnetwork 70, 72, 74, 76 respectively. If a user at node A 62 wanted to engage in a voice conversation with a user at node D 68, then all of the nodes A, B, C, and D 62, 64, 66, 68 would have to honor RSVP requests. If this was the case, then each node 62, 64, 66, 68 would set aside the small bandwidth space for the conversation, at which point the conversation could begin. If any of the nodes in the chain did not honor RSVP requests, then this method would fail.
Voice over IP transmissions have proven to be effective with networks utilizing the IP standard. However, there are many networks which (at least internally) use other techniques instead of or in addition to IP. One of the most common of these techniques is Frame Relay.
Frame relay was designed in response to the increase in high speed, reliable, digital communications mediums. It was originally conceived as an interface for use over ISDN lines, however it has also gained acceptance in other high speed networks. Frame Relay provides for a very simple protocol, since error correcting capability need only be minimal given the high reliability of the communications medium. Additionally, frame relay provides a means for statistically multiplexing many logical data transmissions over a single physical transmission link. This is in sharp contrast to systems which use time-division-multiplexing for supporting multiple data streams. This statistical multiplexing along with the decrease error correcting capability provides more flexible and efficient use of available bandwidth.
FIG. 4 depicts the standard format for the header of a Frame Relay packet 80 (which in Frame Relay is referred to as a frame). The data link connection identifier (DLCI) 80 represents a logical connection that is multiplexed across a physical channel. The command/response (C/R) field 82 is not used by Frame relay but is used by certain applications. The extended address (EA) fields 84a, 84b are each set to 0 if more octets following in the header and 1 if this octet is the last in the header. Any octets beyond the two depicted will contain only DLCI information. The forward explicit congestion notification (FECN) field 86a is set by a network node that is experiencing congestion to notify the device that congestion avoidance procedures should be initiated, while the backward explicit congestion notification (BECN) field 86b informs the originator of the traffic of this condition. The discard eligibility (DE) field 88 is set to 1 if a frame can be disregarding should the system need to begin dropping frames in order to solve congestion problems. The address information is contained within the two-byte address field 84. The two-byte frame check sequence (FCS) field 86 contains characters added to the frame for error control purposes. Finally, data is contained in a variable length data field 88. The data contained in the frame follows this frame header. It is also possible to add a cyclic redundancy check (CRC) or frame check sequence (FCS) field following the data field to aid in error correction.
The inherent problem with this frame design, however, is that it lacks a field describing the delay sensitive or non-delay sensitive nature of the information stored in the data field. Therefore, all information is treated the same, whether it is delay sensitive (voice) or not delay sensitive (data). This issue, particularly the issue of transmitting voice over frame relay, was addressed by the Frame Relay Forum in the FRF.11 standard.
FRF.11 defined a sub-frame structure which could be used to transmit voice communications. The data field of each frame could then contain one or more of the sub-frames. This method is depicted in FIG. 5. In FIG. 5, voice samples 90a, 90b, and 90c are placed in the data fields of sub-frames 92a, 92b, and 92c respectively. Then each sub-frame 92a, 92b, 92c are placed in the information field of a frame 94. The same format is also used to transmit data communications. Data packet 96 is placed in sub-frame 98 which is then placed in the information field of frame 100.
The format of each sub-frame is depicted in FIG. 6. Each sub-frame 110 contains up to four different formats of octets (numbered 1, 2a, 2b, and 2c) of fields. Two of the octets (2b and 2c) are optional. The fields are as follows:
(1) An extension indication (EI) field 112, which is set to indicate the presence of octet 2a. 
(2) A length indication (LI) field 114, which is set to indicate the presence of octet 2b. 
(3) A sub-channel identification (CID) field 116, which indicates the local exchange identification information. This is generally a number between 0 and 255. One number represents data calls. Data calls only require one number to identify the local exchange information because they contain additional headers which represent destination address. Voice calls are each given a unique subchannel identification number (one that is not the number chosen to represent data calls). Thus, in most systems, it is possible to have up to 255 different voice transmissions executing simultaneously. This subchannel identification field may extend into octet 2a if it is present.
(4) A payload type field 118, which indicates the type of payload according to Table 1 illustrated below. The possible types of payload include primary payload transfer syntax (used for voice and data), dialed digit transfer syntax (used for transmitting the digit dialed on a push-button phone), signalling bit transfer syntax (used for standard protocols which are used to establish connection end to end, e.g. between a PBX and a switch or between two switches), fax relay transfer syntax (used for transmitting fax), and primary payload silence indication (used to transmit silence).
(5) Payload length 120, which indicates the number of payload octets following the header.
(6) Payload 122, which contains the data and may extend over more than one octet.
(7) Two unused bits 124a, 124b, which were reserved for some future use.
Thus, for systems that wished to allow voice communications, the format was such that the system could examine each subframe and choose to treat is differently if it contained delay sensitive information rather than non-delay sensitive information (judging from the bits in the subchannel identification field 116). For example, a system may decide to give all delay sensitive information priority over non-delay sensitive information. Thus, anytime voice communications needed to be transmitted, the data communications would have to wait.
However, the FRF.11 standard had some drawbacks. The main drawback was the possibility of starvation of data communications. Starvation occurs when a piece of information is held in a queue for an infinite amount of time, not being allowed to travel across the network because it is considered lower priority information than that being transmitted. Since many systems implementing the FRF.11 standard gave voice communications top priority because of their delay-sensitive nature, there were occasions when data communication experienced long enough delays to create problems for the systems. FIG. 7 depicts an example of where such a situation could occur.
In FIG. 7, frame 132 contains an information field which contains several subframes 134a, 134b, 134c, 134d, 134e, 134f, and 134g. These subframes all contain voice transmissions. Frame 136, on the other hand, contains subframe 138 which contains data information. If voice communications were given top priority over data communications, then frame 130 would have to wait to be transmitted until the entire frame 130 was transmitted over the network. Moreover, if another voice communication was placed in the queue before frame 130 was completely transmitted, then this new voice communication may also take precedence over frame 136. Recent FRF.11 systems have partially solved this problem by cycling between data communications and voice communications. In these systems, after frame 130 was transmitted over the network, then frame 136 would automatically be transmitted no matter what type of information has joined it in the queue. However, the problem of lengthy delays in transmitting small amounts of data still remained.
This problem was addressed by the FRF.12 standard. The FRF.12 standard was created with the realization that, while voice communications are delay sensitive, a small amount of delay can be encountered without creating a problem for these voice communications. It allows for the fragmenting of long IP packets into sequences of shorter sub-frames, which are then placed in frames for transport. It is preferable to place only one of the sub-frames from a particular sequence in each frame, otherwise the effect of fragmentation is diminished. It is, however, possible to place sub-frames from different sequences in the same frame. When the frames are received, the sub-frames are reassembled into the original IP packet. FRF.12 defined three separate fragmentation formats for different types of networks: UNI, NNI, and End-to-End fragmentation. The format for each sub-frame in UNI and NNI is depicted in FIG. 8. The standard Frame Relay header 152, payload 154, and FCS 156 are included in the fragment 150. FRF.12 adds a fragmentation header 158 containing the following fields:
(1) A beginning fragment bit (B) 160 which is set to 1 on the first data fragment of an original frame and set to 0 for all other fragments from that original frame.
(2) An ending fragment bit (E) 162 which is set to 1 on the last data fragment of an original frame and set to 0 for all other fragments from that original frame.
(3) A control bit (C) 164 which is reserved for future control functions.
(4) A sequence number 166 which is a 12-bit binary number that is incremented modulo 212 for each successive fragment of an original frame. This sequence number keeps track of where in the original frame the individual fragments were taken from.
(4) A low order bit 168 which is always set to 1. This bit distinguishes a fragment header from a frame relay header.
The format for each sub-frame in End-to-End fragment is slightly different and is depicted in FIG. 9. The standard frame relay header 182, payload 184, and FCS 186 are included in the sub-frame 180. FRF.12 adds a fragmentation header 188 containing the same fields as the UNI/NNI format. However, the End-to-End fragment also includes an unnumbered information (UI) field 190 (also called a control field), which is used for compatibility purposes with older systems, and a network layer protocol identification (NLPID) field 192 added to the first fragment in a sequence, which stores information on the protocol used by the data within the fragment and allows for multiprotocol interconnection. NLPID fields are discussed in more depth below.
The format for a fragment using both FRF.11 and FRF.12 is depicted in FIG. 10. The same fields present in the End-to-End fragment (shown in FIG. 9) are present, including Frame Relay header 182, payload 184, FCS 186, fragmentation header 188, UI 190 and NLPID fields 192. An FRF.11 sub-frame header 194 is added which contains the exact same information as the sub-frame header in systems using only FRF.11. This format was depicted in FIG. 6.
It is now quite common to have a Frame Relay network connected to the Internet. Thus, many frames now carry data which has already been converted to the IP standard. This is known as IP over Frame Relay, or more generically, multiprotocol interconnect over Frame Relay. Thus each frame can contain sub-frames containing data in the IP standard. In order to deal with these types of frames (as well as frames carrying data converted to standards other than IP), the Frame Relay Forum published a standard called RFC 1490. The main alteration of the sub-frame structure in RFC 1490 is the addition of a field called network layer protocol identification (NLPID). The NLPID field contains a two byte number representing the protocol being used by the data contained within the frame or the sub-frames. This allows the data to be properly converted back to its original form once it is received. The list of commonly used NLPID""s is given in Table 2 below.
Currently, all systems allowing for IP transmissions within a Frame Relay Network use the RFC 1490 standard or something similar. When using this multiprotocol interconnection in systems also using fragmentation (such as FRF.12), the system only stored the NLPID field in the first sub-frame of a sequence (since every sub-frame in the sequence will logically have the same NLPID value). The router then examines the first sub-frame in the sequence to determine its NLPID value. In systems without fragmentation, each sub-frame contains an NLPID value.
While this provides the compatibility required when transmitting IP (or other format) data over a Frame Relay network, the problem of transmitting voice or other delay-sensitive information still exists. If voice data is stored in IP packets (as is the case in Internet transmissions) and these IP packets are passed through a Frame Relay network, there is currently no mechanism in place to allow the Frame Relay network to distinguish between a delay-sensitive IP packet and non-delay sensitive IP packet. This type of transmission is known as voice over IP over Frame Relay and is depicted in FIG. 11. Voice sample 200 first travels over the Internet. Thus, it is placed in an IP packet 202. This IP packet 202 also contains an IP header 204, as depicted in FIG. 2. The IP packet 202, then travels through a Frame Relay network, and is thus placed in a Frame Relay sub-frame 206. The Frame Relay sub-frame 206 also contains a sub-frame header 208 as depicted in FIG. 6. Sub-frame 206 then is placed in a Frame Relay frame 210, which also contains a frame header 212 as depicted in FIG. 4. There are many other embodiments of voice over IP over Frame relay. The embodiment depends on the formats and standards used by the system. For example, a system using RFC 1490 may further split each IP packet into a sequence of sub-frames. However, all IP over Frame Relay embodiments suffer from the same problem, transmitting voice over IP over Frame Relay.
Accordingly, it would be desirable to provide a method for transmitting voice over IP over Frame Relay that would allow the network systems to easily recognize frames or fragments that were carrying delay-sensitive information and give priority to those delay-sensitive frames or fragments.
A method of transmitting delay sensitive information over Internet Protocol (IP) over Frame Relay including storing the information in an IP packet, storing the IP packet in a sub-frame, storing a special symbol representing that the frame is delay sensitive in the sub-frame, storing the sub-frame in a frame, storing a network layer protocol identification representing that the frame contains IP information in the frame, and transmitting the frame over a Frame Relay Network, distinguishing delay sensitive information from non-delay sensitive information by examining the special symbol. Additionally, in systems using the FRF.12 or similar fragmenting standard, the special symbol may be stored in the header of the fragment.